package 二分查找;

public class 非递归与递归二分查找 {
	public static void main(String[] args) {
		
		//一定要是有序数组，才能使用二分查找
		int arr[] = {1,3,5,6,8,9};
		int key = 3;
		
		BinarySort binarySort = new BinarySort();
		
		int binarySortWhile = binarySort.binarySortWhile(arr, key);
		System.out.println(binarySortWhile);
		
		int binarySortRecursive = binarySort.binarySortRecursive(arr, key, 0, arr.length);
		System.out.println(binarySortRecursive);
	}
}
/**
 * 二分查找
 * @author PC
 *
 */
class BinarySort{
	
	/**
	 *  非递归二分查找
	 * @param arr
	 * @param key
	 * @return
	 */
	public int binarySortWhile(int[] arr, int key) {
		//左起点
		int left = 0;
		//右起点
		int right = arr.length -1;
		//循环
		while(left <= right) {
			//中间值
			int mid = (left + right) / 2;
			
			//找到
			if(arr[mid] == key) {
				return mid;
			}
			
			//小于，向右找
			if(arr[mid] < key) {
				left = mid + 1;
			}else {
				//大于，向左找
				right = mid -1;
			}
		}
		//未找到
		return -1;
		
		 /*
			if (key < array[mid]) {
	            high = mid - 1;
	        } else if (key > array[mid]) {
	            low = mid + 1;
	        } else {
	            return mid;
	        }
		 */
	}

	
	/**
	 * 递归二分查找 ， 顺序可以不同，if 左 else if 右 else 找到
	 * @param arr 待查数组
	 * @param key 待查值
	 * @param left 左起点
	 * @param right 右起点
	 * @return
	 */
	public int binarySortRecursive(int[] arr, int key, int left, int right) {
		
		if(left <= right) {
			int mid = (left + right) / 2 ;
			if(arr[mid] == key) {
				return mid;
			}
			
			if(arr[mid] < key) {
				return binarySortRecursive(arr, key, left+1, right);
			}else{
				return binarySortRecursive(arr, key, left, right-1);
			}
		}
		return -1;
		
		/*
  			if (key < array[mid]) {
                return binarySortRecursion(array, key, low, mid - 1);
            } else if (key > array[mid]) {
                return binarySortRecursion(array, key, mid + 1, high);
            } else {
                return mid;
            }
		 */
	}
	
}